package com.kingwood.algorithm.zuochengyun.dandiaozhan;

/**
 * @Author 22025812
 * @Description: TODO
 * @Date: 2024/3/13 15:35
 * @Modified By：
 * @Version 1.0
 */
// 每日温度
// 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer
// 其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后
// 如果气温在这之后都不会升高，请在该位置用 0 来代替。
// 测试链接 : https://leetcode.cn/problems/daily-temperatures/
public class Code02_DailyTemperatures {
    public static int MAXN = 100001;

    public static int[] stack = new int[MAXN];

    public static int r;

    public static int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        r = 0;

        for (int i=0, cur; i<n; i++) {
            while (r > 0 && temperatures[i] > temperatures[stack[r - 1]]) {
                cur = stack[--r];
                answer[cur] = i - cur;
            }

            stack[r++] = i;
        }

        return answer;
    }

    public int[] dailyTemperatures2(int[] T) {
        int length = T.length;
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            int current = T[i];
            for (int j = i + 1; j < length; j++) {
                if (T[j] > current) {
                    result[i] = j - i;
                    break;
                }
            }
        }

        return result;
    }

}
